package com.gitee.feizns.explore.data_structure.graph;

import com.gitee.feizns.explore.data_structure.graph.utils.Graph;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * @author feizns
 * @since 2020/4/27
 */
public class Hamilton {

    private Graph<Integer> graph;

    private int[] pre;

    private int size;

    private int start;

    private int left;

    public Hamilton(int size) {
        this.size = size;
        this.pre = new int[size];
        this.graph = new Graph<>();
        for (int i = 0; i < size; i++)
            pre[i] = -1;
    }

    public void add(int s, int t) {
        if ( s < size && t < size )
            graph.addEdge(s, t);
    }

    public List<Integer> answer(int start) {
        this.start = start;
        left = size;
        List<Integer> ret = new LinkedList<>();
        int dfs = dfs(start, start);
        if ( dfs != -1 ) {
            int tmp = pre[start];
            while ( tmp != start ) {
                ret.add(tmp);
                tmp = pre[tmp];
            }
            Collections.reverse(ret);
            ret.add(start);
            ((LinkedList<Integer>) ret).addFirst(start);
        }
        return ret;
    }

    private int dfs(int c, int p) {
        if ( pre[c] == -1 ) {
            pre[c] = p;
            left--;
            Set<Integer> adj = graph.adj(c);
            for (Integer v : adj) {
                if ( left == 0 && v == start ) {
                    pre[start] = c;
                    return start;
                }
                int dfs = dfs(v, c);
                if ( dfs != -1 )
                    return dfs;
            }
            pre[c] = -1;
            left++;
        }
        return -1;
    }

    public static void main(String[] args) {
        Hamilton hamilton = new Hamilton(4);
        hamilton.add(0, 2);
        hamilton.add(0, 1);
        hamilton.add(2, 1);
        hamilton.add(1, 3);
        System.out.println(hamilton.answer(0));
    }

}
